home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 June / EnigmA AMIGA RUN 08 (1996)(G.R. Edizioni)(IT)[!][issue 1996-06][EARSAN CD VII].iso / earcd / gcc / ixemlsrc.lha / ixemul / ixnet / big.c next >
C/C++ Source or Header  |  1996-03-13  |  10KB  |  385 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)big.c       5.2 (Berkeley) 2/22/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/types.h>
  42. #include <db.h>
  43. #include <stdlib.h>
  44. #include <string.h>
  45. #include "btree.h"
  46. #include "utils.h"
  47. #include "page.h"
  48. /*
  49.  *  _BT_GETBIG -- Get big data from indirect pages.
  50.  *
  51.  *    This routine chases indirect blocks for the big object at the
  52.  *    specified page to a buffer, and return the address of the buffer.
  53.  *
  54.  *    Parameters:
  55.  *        t -- btree with the indirect blocks
  56.  *        pgno -- page number that starts the chain
  57.  *        p -- (char **) to get the address of the buffer containing
  58.  *             the key or datum.
  59.  *        sz -- pointer to an int to get the size of the instantiated
  60.  *              object.
  61.  *
  62.  *    Returns:
  63.  *        RET_SUCCESS, RET_ERROR.
  64.  *
  65.  *    Side Effects:
  66.  *        None.
  67.  */
  68.  
  69. int
  70. _bt_getbig(t, pgno, p, sz)
  71.     BTREE_P t;
  72.     pgno_t pgno;
  73.     char **p;
  74.     int *sz;
  75. {
  76.     pgno_t save;
  77.     size_t nbytes;
  78.     size_t nhere;
  79.     BTHEADER *h;
  80.     char *top, *from, *where;
  81.  
  82.     save = t->bt_curpage->h_pgno;
  83.     if (_bt_getpage(t, pgno) == RET_ERROR)
  84.         return (RET_ERROR);
  85.  
  86.     h = t->bt_curpage;
  87.  
  88.     bcopy((char *) &(h->h_linp[0]),
  89.           (char *) &nbytes,
  90.           (size_t) sizeof(nbytes));
  91.  
  92.     if ((*p = (char *) malloc(nbytes)) == (char *) NULL)
  93.         return (RET_ERROR);
  94.  
  95.     *sz = nbytes;
  96.     from = ((char *) (&h->h_linp[0])) + sizeof(nbytes);
  97.     top = ((char *) h) + t->bt_psize;
  98.  
  99.     /* need more space for data? */
  100.  
  101.     where = *p;
  102.  
  103.     while (nbytes > 0) {
  104.         nhere = (int) (top - from);
  105.         if (nhere > nbytes) {
  106.             (void) bcopy(from, where, (size_t) nbytes);
  107.             nbytes = 0;
  108.         } else {
  109.             (void) bcopy(from, where, nhere);
  110.             where += nhere;
  111.             nbytes -= nhere;
  112.             if (_bt_getpage(t, h->h_nextpg) == RET_ERROR)
  113.                 return (RET_ERROR);
  114.             h = t->bt_curpage;
  115.             top = ((char *) h) + t->bt_psize;
  116.             from = (char *) &(h->h_linp[0]);
  117.         }
  118.     }
  119.  
  120.     if (_bt_getpage(t, save) == RET_ERROR)
  121.         return (RET_ERROR);
  122.  
  123.     return (RET_SUCCESS);
  124. }
  125.  
  126. /*
  127.  *  _BT_DELINDIR -- Delete a chain of indirect blocks from the btree.
  128.  *
  129.  *    When a large item is deleted from the tree, this routine puts the
  130.  *    space that it occupied onto the free list for later reuse.  The
  131.  *    bt_free entry in the btree structure points at the head of this list.
  132.  *    This value is also stored on disk in the btree's metadata.
  133.  *
  134.  *    Parameters:
  135.  *        t -- btree from which to delete pages
  136.  *        chain -- page number that starts the chain.
  137.  *
  138.  *    Returns:
  139.  *        RET_SUCCESS, RET_ERROR.
  140.  *
  141.  *    Side Effects:
  142.  *        Invalidates the current on-disk version of the btree's
  143.  *        metadata (if any), and updates the free list appropriately.
  144.  */
  145.  
  146. int
  147. _bt_delindir(t, chain)
  148.     BTREE_P t;
  149.     pgno_t chain;
  150. {
  151.     BTHEADER *h;
  152.     pgno_t save;
  153.     pgno_t oldfree;
  154.  
  155.     h = t->bt_curpage;
  156.     save = h->h_pgno;
  157.     if (_bt_getpage(t, chain) == RET_ERROR)
  158.         return (RET_ERROR);
  159.  
  160.     /*
  161.      *  If some internal node is pointing at this chain, don't
  162.      *  delete it.
  163.      */
  164.  
  165.     if (t->bt_curpage->h_flags & F_PRESERVE) {
  166.         if (_bt_getpage(t, save) == RET_ERROR)
  167.             return (RET_ERROR);
  168.         return (RET_SUCCESS);
  169.     }
  170.  
  171.     /* if there's nothing on the free list, this is easy... */
  172.     if (t->bt_free == P_NONE) {
  173.         t->bt_free = chain;
  174.     } else {
  175.         oldfree = t->bt_free;
  176.  
  177.         /* find the end of the data chain for the deleted datum */
  178.         t->bt_free = chain;
  179.         do {
  180.             if (_bt_getpage(t, chain) == RET_ERROR)
  181.                 return (RET_ERROR);
  182.             h = t->bt_curpage;
  183.             if (h->h_nextpg != P_NONE)
  184.                 chain = h->h_nextpg;
  185.         } while (h->h_nextpg != P_NONE);
  186.  
  187.         /* link freed pages into free list */
  188.         h->h_nextpg = oldfree;
  189.         if (_bt_write(t, h, RELEASE) == RET_ERROR)
  190.             return (RET_ERROR);
  191.         if (_bt_getpage(t, oldfree) == RET_ERROR)
  192.             return (RET_ERROR);
  193.         h = t->bt_curpage;
  194.         h->h_prevpg = chain;
  195.         if (_bt_write(t, h, RELEASE) == RET_ERROR)
  196.             return (RET_ERROR);
  197.     }
  198.  
  199.     /* restore the tree's current page pointer */
  200.     if (_bt_getpage(t, save) == RET_ERROR)
  201.         return (RET_ERROR);
  202.  
  203.     /* we have trashed the tree metadata; rewrite it later */
  204.     t->bt_flags &= ~BTF_METAOK;
  205.  
  206.     return (RET_SUCCESS);
  207. }
  208.  
  209. /*
  210.  *  _BT_INDIRECT -- Write a series of indirect pages for big objects.
  211.  *
  212.  *    A chain of indirect pages looks like
  213.  *
  214.  *       +-------------------+   +---------------------+
  215.  *       |hdr|size|           |   |hdr|         |
  216.  *       +---+----+           |   +---+         |
  217.  *       |   ... data ...    |   |   ... data ...     |    ...
  218.  *       |               |   |             |
  219.  *       +-------------------+   +---------------------+
  220.  *
  221.  *    where hdr is a standard btree page header (with the indirect bit
  222.  *    set), size on the first page is the real size of the datum, and
  223.  *    data are bytes of the datum, split across as many pages as necessary.
  224.  *    Indirect pages are chained together with the h_prevpg and h_nextpg
  225.  *    entries of the page header struct.
  226.  *
  227.  *    A single DBT is written per chain, so space on the last page is
  228.  *    wasted.
  229.  *
  230.  *    We return the page number of the start of the chain.
  231.  *
  232.  *    When a big object is deleted from a tree, the space that it occupied
  233.  *    is placed on a free list for later reuse.  This routine checks that
  234.  *    free list before allocating new pages to the big datum being inserted.
  235.  *
  236.  *    Parameters:
  237.  *        t -- btree in which to store indirect blocks
  238.  *        data -- DBT with the big datum in it
  239.  *        pgno -- place to put the starting page number of the chain
  240.  *
  241.  *    Returns:
  242.  *        RET_SUCCESS, RET_ERROR.
  243.  *
  244.  *    Side Effects:
  245.  *        Current page is changed on return.
  246.  */
  247.  
  248. int
  249. _bt_indirect(t, data, pgno)
  250.     BTREE_P t;
  251.     DBT *data;
  252.     pgno_t *pgno;
  253. {
  254.     pgno_t prev;
  255.     char *top;
  256.     char *where;
  257.     char *from;
  258.     size_t dsize;
  259.     pgno_t nextchn;
  260.     int ischain;
  261.     BTHEADER *cur;
  262.  
  263.     /* get set for first page in chain */
  264.     prev = P_NONE;
  265.     dsize = data->size;
  266.     from = (char *) data->data;
  267.  
  268.     /* if there are blocks on the free list, use them first */
  269.     if ((*pgno = t->bt_free) == P_NONE) {
  270.         if ((cur = _bt_allocpg(t)) == (BTHEADER *) NULL)
  271.             return (RET_ERROR);
  272.  
  273.         ischain = 0;
  274.         *pgno = cur->h_pgno = ++(t->bt_npages);
  275.     } else {
  276.         if (_bt_getpage(t, *pgno) == RET_ERROR)
  277.             return (RET_ERROR);
  278.         ischain = 1;
  279.         cur = t->bt_curpage;
  280.     }
  281.  
  282.     cur->h_flags = F_CONT|F_LEAF;
  283.     (void) bcopy((char *) &dsize, (char *) &cur->h_linp[0], sizeof(size_t));
  284.     where = ((char *) (&cur->h_linp[0])) + sizeof(size_t);
  285.  
  286.     /* fill and write pages in the chain */
  287.     for (;;) {
  288.         int nhere;
  289.  
  290.         top = ((char *) cur) + t->bt_psize;
  291.         cur->h_prevpg = prev;
  292.         nextchn = cur->h_nextpg;
  293.         nhere = (int) (top - where);
  294.  
  295.         if (nhere >= dsize) {
  296.             (void) bcopy(from, where, (int) dsize);
  297.             cur->h_nextpg = P_NONE;
  298.             dsize = 0;
  299.         } else {
  300.             (void) bcopy(from, where, (int) nhere);
  301.             dsize -= nhere;
  302.             from += nhere;
  303.             if (nextchn == P_NONE)
  304.                 cur->h_nextpg = t->bt_npages + 1;
  305.             prev = cur->h_pgno;
  306.         }
  307.  
  308.         /* current page is ready to go; write it out */
  309.         if (_bt_write(t, cur, RELEASE) == RET_ERROR)
  310.             return (RET_ERROR);
  311.  
  312.         /* free the current page, if appropriate */
  313.         if (IS_A_DISK(t) && !ISCACHE(t) && !ischain) {
  314.             (void) free ((char *) cur);
  315.         }
  316.  
  317.         /* done? */
  318.         if (dsize == 0)
  319.             break;
  320.  
  321.         /* allocate another page */
  322.         if (nextchn == P_NONE) {
  323.             if ((cur = _bt_allocpg(t)) == (BTHEADER *) NULL)
  324.                 return (RET_ERROR);
  325.             ischain = 0;
  326.             cur->h_pgno = ++(t->bt_npages);
  327.         } else {
  328.             if (_bt_getpage(t, nextchn) == RET_ERROR)
  329.                 return (RET_ERROR);
  330.             ischain = 1;
  331.             cur = t->bt_curpage;
  332.         }
  333.         cur->h_flags = F_LEAF | F_CONT;
  334.  
  335.         where = (char *) (&cur->h_linp[0]);
  336.     }
  337.  
  338.     /* if we used pages from the free list, record changes to it */
  339.     if (*pgno == t->bt_free) {
  340.         t->bt_free = nextchn;
  341.         t->bt_flags &= ~BTF_METAOK;
  342.     }
  343.  
  344.     return (RET_SUCCESS);
  345. }
  346.  
  347. /*
  348.  *  _BT_MARKCHAIN -- Mark a chain of pages as used by an internal node.
  349.  *
  350.  *    Chains of indirect blocks pointed to by leaf nodes get reclaimed
  351.  *    when the item that points to them gets deleted.  Chains pointed
  352.  *    to by internal nodes never get deleted.  This routine marks a
  353.  *    chain as pointed to by an internal node.
  354.  *
  355.  *    Parameters:
  356.  *        t -- tree in which to mark
  357.  *        chain -- number of first page in chain
  358.  *
  359.  *    Returns:
  360.  *        RET_SUCCESS, RET_ERROR.
  361.  *
  362.  *    Side Effects:
  363.  *        None.
  364.  */
  365.  
  366. int
  367. _bt_markchain(t, chain)
  368.     BTREE_P t;
  369.     pgno_t chain;
  370. {
  371.     pgno_t save;
  372.  
  373.     save = t->bt_curpage->h_pgno;
  374.  
  375.     if (_bt_getpage(t, chain) == RET_ERROR)
  376.         return (RET_ERROR);
  377.  
  378.     t->bt_curpage->h_flags |= (F_DIRTY|F_PRESERVE);
  379.  
  380.     if (_bt_getpage(t, save) == RET_ERROR)
  381.         return (RET_ERROR);
  382.  
  383.     return (RET_SUCCESS);
  384. }
  385.